package math.数列.等差数列;

import static algorithm.二分.快速幂.quickPower;

public class Formula {
    //region 等差 求模 模板
    static int sumFormula1(long start, long end, long diff, int mod) {
        if((end-start)%diff!=0) {
            throw new RuntimeException(String.format("非法等差数列,start:%s,end:%s,diff%s,mod:%s", start,end,diff,mod));
        }
        long items = (end - start) /diff+1;
        long tmp = (int)(((start%mod+end%mod)*(items%mod))%mod);
        long inv2 = inv(2,mod);
        return (int)((tmp*inv2)%mod);
    }

    static int inv(int num,int mod) {
        return quickPower(num,mod-2,mod);
    }
    static int quickPower(int base, int power, int mod) {
        long res = 1;
        long b = base;
        while (power > 0) {
            if (power % 2 != 0) {
                res *= b;
                res %= mod;
            }
            b *= b;
            b %= mod;
            power >>= 1;
        }
        return (int) (res % mod);
    }
    //endregion

}
